#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

// 2583. 二叉树中的第 K 大层和
// 给你一棵二叉树的根节点 root 和一个正整数 k 。
//树中的 层和 是指 同一层 上节点值的总和。
//返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x):val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {}
};
class Solution {
private:
    priority_queue<pair<long long, int>> pq;
    map<int,long long > record;  // h : sum
    void kthLargestLevelSum(TreeNode* root, int k, int h) {
        if(root == nullptr)
            return;
//        cout <<"root:" << root->val << ",h:" << h << endl;
        if(record.count(h) == 0) {
            record[h] = root->val;
        } else {
            record[h] = record[h] + root->val;
        }
        kthLargestLevelSum(root->left,k,h+1);
        kthLargestLevelSum(root->right,k,h+1);
    }
public:
    long long kthLargestLevelSum(TreeNode* root, int k) {
        kthLargestLevelSum(root,k,1);
        int count = 0;
        long long res = -1;
        for(auto iter = record.begin();iter != record.end(); iter++) {
//            cout << iter->first << ":" << iter->second << endl;
            pq.push(make_pair(iter->second,iter->first));
        }
//        cout << "pq输出:" << endl;
        while (!pq.empty()) {
            count++;
            pair<long long,int> p = pq.top();
//            cout << p.second << ":" << p.first << endl;
            pq.pop();
            if(count == k) {
                res = p.first;
                break;
            }
        }
        return res;
    }
};
int main() {
    TreeNode* root1 = new TreeNode(5,
                                   new TreeNode(8,
                                                new TreeNode(2,new TreeNode(4),new TreeNode(6)),
                                                new TreeNode(1)
                                                ),
                                   new TreeNode(9,new TreeNode(3),new TreeNode(7))
                                   );
    cout << Solution().kthLargestLevelSum(root1,2) << endl;
    return 0;
}
